
struct ListNode
{
    int val;
    struct ListNode *next;
};
class Solution
{
  public:
    ListNode *Merge(ListNode *pHead1, ListNode *pHead2)
    {
        //新链表的结点，用来给新链表添加元素
        ListNode *add = new (ListNode);
        add->next = nullptr;
        //保存好新链表的头结点
        ListNode *head = add;
        ListNode *tmp1 = pHead1;
        ListNode *tmp2 = pHead2;
        while (tmp1 && tmp2)
        {
            if (tmp1->val < tmp2->val)
            {
                add->next = tmp1;
                tmp1 = tmp1->next;
            }
            else
            {
                add->next = tmp2;
                tmp2 = tmp2->next;
            }
            add = add->next;
        }
        //非空的直接接在后面，因为已经是排列好的了
        add->next = tmp1 == nullptr ? tmp2 : tmp1;
        return head->next;
    }
};